import java.util.ArrayList;
import java.util.List;

/**
 * 递增顺序的搜索树
 * https://leetcode.cn/problems/NYBBNL/submissions/518901579/
 * 先将搜索树按照中序遍历存储到链表中，然后再遍历链表，插入到新的搜索树中
 */
class Solution5 {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> arrayList = new ArrayList<>();
        func(root,arrayList);


        TreeNode demo = new TreeNode(-1);
        TreeNode cur = demo;
        for (int val:arrayList) {
            cur.right = new TreeNode(val);
            cur = cur.right;
        }
        return demo.right;
    }

    private void func(TreeNode root,  List<Integer> arrayList) {
        if(root == null) {
            return ;
        }
        func(root.left,arrayList);
        arrayList.add(root.val);
        func(root.right,arrayList);
    }
}